This invention relates to a production system represented by an expert system and more particularly to a tool for forward reasoning and a high-speed inference method using the tool.
In the past, the production system widely used as a tool for implementing the expert system includes, as shown in FIG. 2, a production memory 2-1 for storing rules, a working memory 2-2 for storing data necessary for execution of the rules, and an interpreter (inference engine) 2-3 which performs interpretation and execution by referring to or looking up the above two memories. Fundamentally, the interpreter repeats three cycles of pattern matching, conflict resolution and execution to perform execution processing repeatedly until no executable rule subsists. When data such as a frame representative of a fact is first supplied to the working memory, the pattern matching cycle proceeds wherein pattern matching is effected between a condition part of each of all the rules and the contents of the working memory at that time, so that for each rule, an executable condition constructed of a combination of facts may be created which makes the rule in question executable and satisfies the rule condition part. Subsequently, in the conflict resolution cycle, one executable condition is selected from the executable conditions of all rules in accordance with a certain strategy and a rule to which the selected executable condition belongs is selected. Finally, in the execution cycle, an execution part of the selected rule is executed on the basis of the selected executable condition to modify the facts stored in the working memory. The "certain strategy" referred to herein signifies a stipulation which determines the sequence of execution of rules in accordance with, for example, the time that the rule executable condition is created (time tag). The time-tag stipulation is derived from the thinking purporting that "inference based on a newly created executable condition (facts) can be done with higher efficiency".
In the production system outlined as above, the pattern matching processing is effected for all rules each time the pattern matching cycle is executed with the result that the same processing is repeated, thus degrading the processing efficiency. Under the circumstances, RETE algorithm has been proposed which is effective to reduce the number of operations of pattern matching between rule and fact. This algorithm is pattern matching algorithm practically used in many famous commercial tools such as OPS 5, ART, KBMS and ES/KERNEL.
Pursuant to the RETE algorithm, the rule condition part is converted into a data flow graph called a RETE network having nodes at which pattern decision commands are placed, and the data flow graph is so optimized as to eliminate the same pattern decision occurring among a plurality of rules. Further, the pattern decision is not repeated every cycle but the results obtained midway in calculation for the previous cycle are all conserved on the network, and only changes resulting from execution of the rules are subjected to pattern matching.
As is clear from the above, the RETE algorithm is highly efficient but conventionally, this algorithm has been practiced by expressing nodes of the network in terms of intermediate language form such as a list and a table and by causing an interpreter to perform interpretation and execution, thus raising a problem that satisfactory performance can not be realized.
To cope with this problem, a method such as OPS 83 has recently been employed by which the RETE network is converted into a direct procedure (Reference literature: Technique for Increasing the Speed of Production System by Tohru Ishida and Kazuhiro Kuwahara, Trans. Information Processing Society of Japan, Vol. 29, No. May 5, 1988).
The prior art described hereinbefore may be summarized as shown in FIG. 3. To explain, in place of decreasing the number of pattern matching operations at the condition part of each rule, an executable condition for the rule is conserved and besides intermediate results are also conserved on the RETE network as indicated at block 3-1 so that only modified frames may be again subjected to pattern matching. Also, by making a plurality of rules have common conditions in common in the network as indicated at block 3-2, the number of pattern decision operations can be reduced considerably to advantage.
However, where a great number of modified frames are present on the network, the prior art method suffers from a disadvantage that as indicated at block 3-3, all of the rule executable conditions and intermediate results must be modified and memory control is required for this purpose.
For example, a program consisting of rules and frames as shown in FIG. 4 can be converted into a RETE network, as shown in FIG. 5. A rule 1 of this program has the meaning of "If for an instance frame having a class name of fb, values of its attribute d are substituted into variables Y and X and for an instance having a class name of fa, the value of its attribute b is smaller than 10 and its frame name is substituted into variable Z" and statements following "then" constitute an execution part of the rule 1. A rule 2 is similar and its explanation will be omitted. As for the frame, there are two clase frames fa and fb and instance frames fa.sub.1, fb.sub.1 and fb.sub.2. The initial value of attribute of the instance frame is the same as that of the class frame.
When examining features of this program in view of the RETE algorithm, the program will be proved to feature that conditions in the rule 1 resemble those in rule 2, thus permitting the program to be converted into a highly efficient RETE network in which the rules 1 and 2 can have common conditions in common, and that the frame name referred to in the rule condition part is represented by the variable so as to generate a plurality of intermediate results to be conserved on the network frame, thus reducing the number of pattern matching operations greatly. In effect, on the FIG. 5 RETE network, the rules 1 and 2 have the first condition of the rule 1 and the second condition of the rule 2 as well as the second condition of the rule 1 and the first condition of the rule 2 in common and the pattern decision results are conserved as intermediate results at SUB-TERM's and MERGE's on the network.
Consequently, the number of pattern decision operations effected when a frame referred to by the rule condition part is modified can be reduced considerably. For example, when the instance frame fa.sub.1 is modified, one matching decision operation is carried out at INTRA 1 of the first condition of the rule 1 but in the rule 2, only reference to intermediate results is made at SUB-TERM and therefore no matching decision is carried out. Accordingly, the number of matching decision operations is one in total.
However, this program is considered as one of programs which degrade the performance pursuant to the RETE algorithm the most. This is because while the number of matching decision operations can be reduced, it takes a long time to modify the intermediate results. For example, when fa.sub.1 is modified, all intermediate results inclusive of fa.sub.1 and conserved on the RETE network at two SUB-TERM's, MERGE, and RULE-TERM in the rule 1 and at MERGE and RULE-TERM in the rule 2 must be retrieved and deleted and besides new intermediate results must be prepared on the network.
As is clear from the above, the conservation of the intermediate results on the network is good for one thing but bad for another thing and it is risky to simply use only the number of pattern decision operations as an evaluation criterion for algorithm. Thus, in order to evaluate the RETE algorithm, two evaluation criteria are required including the number of pattern decision operations and the amount of modification of the intermediate results.
Another problem is encountered in the RETE algorithm in connection with implementation of the algorithm. Since in the RETE algorithm a data driving type execution mechanism is employed in which a modified frame is "drawn" into the network in accordance with a data flow model, a data flows computer must be realized virtually with an interpreter program (inference engine program) in implementing the RETE algorithm on an ordinary pipe-line computer and virtual instructions arranged on a rule network must be interpreted and executed by means of the interpreter. Thus, the virtual instructions have to be executed through the medium of the interpreter and disadvantageously, inference can not be executed with high efficiency. Under the circumstances, a system for increasing the processing speed has hitherto been available wherein pattern decision commands on the RETE network are converted into a machine language instruction set for computer. However, in a large-scale system in which the number of frames amounts up to several of thousands to several of ten thousands, the frame per se is expressed in terms of a table form such as a list and data, and therefore pointers are frequently brought into use in order to make reference to a frame and the frame reference operation disadvantageously causes a bottleneck in attaining satisfactory inference performance.